#ifndef SORT_H
#define SORT_H

#include "config.h"

/*! 
 * 插入排序
 * 
 * 一般来说，插入排序都采用in-place在数组上实现。
 * 具体算法描述如下：
 * 1.从第一个元素开始，该元素可以认为已经被排序
 * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置
 * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * 5.将新元素插入到该位置后
 * 6.重复步骤2~5
 *
 */
double SortInsertion(int *data, size_t size);



/*!
 * 选择排序
 * 
 * 选择排序(Selection sort)是一种简单直观的排序算法。
 * 它的工作原理如下。首先在未排序序列中找到最小（大）元素，
 * 存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，
 * 然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
 * 选择排序的主要优点与数据移动有关。
 * 如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，
 * 它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。
 * 在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
 * 
 */
double SortSelection(int *data, size_t size);



/*!
 * 冒泡排序
 * 
 * 冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。
 * 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
 * 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
 * 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 * 冒泡排序对n个项目需要O(n^2)的比较次数，且可以原地排序。
 * 尽管这个算法是最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。
 * 冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。
 * 在最坏的情况，冒泡排序需要O(n^2)次交换，而插入排序只要最多O(n)交换。
 * 冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（O(n^2)），而插入排序在这个例子只需要O(n)个运算。
 * 因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。
 * 冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到O(n)。
 * 在这个情况，在已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序和比较大小反过来，也可以稍微地改进效率。
 * 有时候称为往返排序，因为算法会从数列的一端到另一端之间穿梭往返。
 * 
 * 冒泡排序算法的运作如下：
 * 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 * 3.针对所有的元素重复以上的步骤，除了最后一个。
 * 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */
double SortBubble(int *data, size_t size);


/*!
 * 快速排序
 * 
 * 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。
 * 在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，
 * 因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
 * 
 * 快速排序是二叉查找树（二叉查找树）的一个空间优化版本。
 * 不是循序地把数据项插入到一个明确的树中，而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。
 * 这两个算法完全地产生相同的比较次数，但是顺序不同。
 * 对于排序算法的稳定性指标，原地分区版本的快速排序算法是不稳定的。
 * 其他变种是可以通过牺牲性能和空间来维护稳定性的。
 * 快速排序的最直接竞争者是堆排序（Heapsort）。
 * 堆排序通常比快速排序稍微慢，但是最坏情况的运行时间总是O(n log n)。
 * 快速排序是经常比较快，除了introsort变化版本外，仍然有最坏情况性能的机会。
 * 如果事先知道堆排序将会是需要使用的，那么直接地使用堆排序比等待 introsort 再切换到它还要快。
 * 堆排序也拥有重要的特点，仅使用固定额外的空间（堆排序是原地排序），而即使是最佳的快速排序变化版本也需要Θ(log n)的空间。
 * 然而，堆排序需要有效率的随机存取才能变成可行。
 * 快速排序也与归并排序（Mergesort）竞争，这是另外一种递归排序算法，但有坏情况O(n log n)运行时间的优势。
 * 不像快速排序或堆排序，归并排序是一个稳定排序，
 * 且可以轻易地被采用在链表（linked list）和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。
 * 尽管快速排序可以被重新改写使用在炼串行上，但是它通常会因为无法随机存取而导致差的基准选择。
 * 归并排序的主要缺点，是在最佳情况下需要Ω(n)额外的空间。
 * 
 * 步骤为：
 * 从数列中挑出一个元素，称为 "基准"（pivot），
 * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 * 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
 * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 */
 double SortQuick(int *data, size_t size);

#endif // SORT_H
